動態規劃基礎 這篇是書中1-2節

動態規劃(Dynamic Programming)的問題時許多人的難關，因為動態規劃的問題通常不是很直觀，解題的思路也有需要稍微轉換，因此常常卡住思路．

其實，動態規劃可以當成一種”求極值”的表現．動態規劃是運籌學內的最佳化方法之一，只是在程式碼演算法上常常使用到．

既然我們將動態規劃看作是”求極值”，那其核心問題，就在”如何列舉”上面．我們只要可以將所有的可行答案列出，然後將其中的極值找出．養成遇到動態規劃問題，先思考如何列舉出全部的結果．

既然這麼簡單，為什麼動態規劃會成為一大難關呢．

主要是動態規劃問題通常不會容易列舉出來，而是會在其中有複數的重疊子問題．如果直接暴力將所有可能列出，效率會極其低下，所以會配合一些技巧，例如 “備忘錄” “DP Table”來輔助子問題的列舉問題．

而藉由我們所找到的極值．專有名詞為”最佳子結構”，我們可以從局部問題的極值推廣到整體問題．

動態規劃只能應用於有最佳子結構的問題。最佳子結構的意思是局部最佳解能決定全域最佳解（對有些問題這個要求並不能完全滿足，故有時需要引入一定的近似）。簡單地說，問題能夠分解成子問題來解決。— From Wiki

而如何到達最佳子結構，則是需要另外一個要素，便是如何從上個狀態到達下個狀態，稱為”狀態轉移方程”

因此一個動態規劃問題，可以分成三個重點
1.重疊子問題

2.狀態轉移方程(這是最困難的)

3.最佳子結構

所以，解決一個動態規劃問題，大概可以用以下的流程

1.先描述這個問題的最簡單狀態

2.這個問題會有什麼狀態

3.做了什麼選擇，讓狀態改變，到達下一個狀態

4.定義狀態與函數，用來描述選擇與狀態

之後我們會用費波那契數列問題來實際展示動態規劃是怎麼做的．